Three-dimensional (3D) laser scanners and digitizers can be used successfully in applications such as reverse engineering. However, the data they generate, typically a series of x, y, z elements that which make up a point cloud, can be incompatible with many computer-aided-design (CAD) products. Moreover, many conventional CAD products have difficulty converting point cloud data into polygonal models or other modeling formats that can be used with conventional CAD products.
To address these limitations, tools have been designed to support more general geometric parameters including parametric surfaces. An example of a parametric surface includes non-uniform rational B-spline (NURBS) surfaces which are useful in CAD and computer-aided-manufacture (CAM) applications. One example of a tool for representing arbitrary parametric surfaces is disclosed in U.S. Pat. No. 5,555,356 to Scheibl, entitled “System and Method for Generating a Trimmed Parametric Surface for Display on a Graphic Display Device.” In particular, the '356 patent discloses a method and system for representing an arbitrary parametric surface having one or more trimming polylines applied thereto. A quadrangular mesh coextensive with the parametric surface is generated. The quadrangular mesh has a plurality of edges and vertices coinciding with the line segments and points of the trimming polylines. In order to generate the quadrangular mesh, a two-dimensional array of U, V values is defined, wherein points in the array are adjusted to include the points of the trimming polylines. After all the points needing adjustment are adjusted, the points in the array are evaluated, thereby creating geometric coordinate values for each point in the array.
U.S. Pat. No. 5,903,458 to Stewart et al., entitled “System and Method for Forming Geometric Features Using Global Reparametrization,” discloses a method that incorporates a global surface reparametrization scheme for the purposes of extending a conventional manipulation method to applications involving multiple surfaces and for reducing the geometric effect of parametric space distortions on surface features. This method reparametrizes multiple surface patches with a shared two-dimensional space defined in the object space of the model. The result is a geometrically consistent mesh, called a super-mesh, that serves as a global, uniform parametric space for topologically-disconnected, geometrically-disproportional surface patches. Spherical projection is also employed to perform patch reparametrization.
U.S. Pat. No. 5,923,573 to Hatanaka, entitled, “Three-Dimensional CAD System for Producing a Three-Dimensional Model,” discloses kit models that have geometric shape data such as points, curved lines and curved surfaces as well as correlation data which indicates correlation of the geometric shape data. Responsive to modification information, a modification unit modifies the kit model. When a curved line within the geometric shape data is modified, other curved lines which intersect the modified curved line (as well as other components such as curved surfaces which include the modified curved line as a boundary line) are detected based on the correlation data and are modified accordingly. The modification unit moves or changes the object line based on the modification data and modifies, as the object line is modified, all points, curved lines and curved surfaces which intersect the object line. In this manner, a three-dimensional model is formed by modifying kit models stored in memory.
U.S. Pat. No. 5,552,992 to Hunter, entitled “Method and System for Reproduction of an Article From a Physical Model,” discloses a method which uses a first algorithm implemented at an engineering workstation to create a first set of equations which represent a three-dimensional surface of the model from scan data. A second algorithm uses known wire frame data for a part (corresponding to the model) to compute a second set of mathematical equations. The wire frame data defines the various boundaries of the part and includes trim line data and feature line data. The first and second set of equations represent surfaces and characteristics of the model in a recorded format usable by CAD systems.
Attempts have also been made to address limitations associated with rendering complex geometric models at interactive rates. For example, U.S. Pat. No. 5,966,140 to Popovic et al., entitled “Method for Creating Progressive Simplicial Complexes,” discloses a method for creating a generalized representation of an arbitrary geometric model using a progressive simplicial complex that permits topological changes in a geometric model. This method is described in the '140 patent as eliminating the conventional problem of rendering complex geometric models when the progressive mesh representations are all constrained to have the same topological type and, therefore, cannot be simplified into lower dimensional representations. Commonly assigned U.S. Pat. Nos. 5,929,860, 5,963,209, 5,966,133 and 6,046,744 to Hoppe also disclose techniques for constructing progressive meshes and for encoding, transmitting and refining progressive meshes.
Notwithstanding these prior art attempts to generate computer models of objects and surfaces thereon, there still continues to be a need for methods, apparatus and computer program products that can automatically translate polygonal models of objects having triangulated surfaces into watertight NURBS surfaces while simultaneously detecting and preserving character lines and points in an efficient manner.